public class Deque<T> {
	public class List {
		private T data;
		private List next;

		List(T newData) {
			data = newData;
			next = null;
		}
	}

	Deque() {
		top = null;
	}

	private List top;

	public void pushTop(T newData) {
		List temp = new List(newData);
		temp.next = top;
		top = temp;
	}

	public T popTop() {
		T tempData;
		if (top == null)
			return null;
		tempData = top.data;
		top = top.next;
		return tempData;
	}

	public List goPenultimate() {
		if (top == null)
			return null;
		if (top.next == null)
			return top;
		List temp = top;
		while (temp.next.next != null)
			temp = temp.next;
		return temp;
	}

	public T popEnd() {
		List temp = goPenultimate();
		if (temp == null)
			return null;
		if (temp.next == null) {
			top = null;
			return temp.data;
		}
		List temp2 = temp.next;
		temp.next = null;
		return temp2.data;
	}

	public void pushEnd(T newData) {
		List newNode = new List(newData);
		List temp2 = goPenultimate();
		if (temp2 == null) {
			top = newNode;
			return;
		}
		if (temp2.next == null) {
			temp2.next = newNode;
			return;
		}
		temp2 = temp2.next;
		temp2.next = newNode;
	}

	public T showEnd() {
		List temp = goPenultimate();
		if (temp == null)
			return null;
		if (temp.next != null)
			temp = temp.next;
		return temp.data;
	}

	public T showTop() {
		if (top == null)
			return null;
		return top.data;
	}
}
